package com.LC.快排;

//因为每一轮最后一个数一定要比基数小（为了跟右边的基数交换位置），所以必须右边的先走
// 。如果左边的先走，那么每一轮最后一个必然是比基数大的数，这样就无法使基数与这个数相交换。
class Solution{
    public static void main(String[] args) {
        int[] array={1,2,3,4,5,6,7,8,9,10};
        quickSort(array);
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
    public static void quickSort(int[]array){
        int len;
        if(array==null
                ||(len=array.length)==0
                ||len==1){
            return;
        }
        sort(array,0,len-1);
    }


    public static void sort(int[]array,int left,int right){
        if(left>right){
            return;
        }
        // base中存放基准数
        int base=array[left];
        int i=left,j=right;
        while(i!=j){
            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while(array[j]>=base&&i<j){
                j--;
            }
            // 再从左往右边找，直到找到比base值大的数
            while(array[i]<=base&&i<j){
                i++;
            }
            // 上面的循环结束表示找到了位置或者(i>=j，交换两个数在数组中的位置
            if(i<j){
                int tmp=array[i];
                array[i]=array[j];
                array[j]=tmp;
            }
        }
        // 将基准数放到中间的位置（基准数归位）
        array[left]=array[i];
        array[i]=base;
        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        sort(array,left,i-1);
        sort(array,i+1,right);
    }
}